home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / idictdef.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  4.9 KB  |  123 lines
  1. /* Copyright (C) 1998 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: idictdef.h,v 1.2 2000/09/19 19:00:43 lpd Exp $ */
  20. /* Internals of dictionary implementation */
  21.  
  22. #ifndef idictdef_INCLUDED
  23. #  define idictdef_INCLUDED
  24.  
  25. /*
  26.  * A dictionary of capacity M is a structure containing the following
  27.  * elements (refs):
  28.  *
  29.  *      keys - a t_shortarray or t_array of M+1 elements, containing
  30.  *      the keys.
  31.  *
  32.  *      values - a t_array of M+1 elements, containing the values.
  33.  *
  34.  *      count - a t_integer whose value tells how many entries are
  35.  *      occupied (N).
  36.  *
  37.  *      maxlength - a t_integer whose value gives the client's view of
  38.  *      the capacity (C).  C may be less than M (see below).
  39.  *
  40.  *      memory - a foreign t_struct referencing the allocator used to
  41.  *      create this dictionary, which will also be used to expand or
  42.  *      unpack it if necessary.
  43.  *
  44.  * C < M is possible because on large-memory systems, we usually round up M
  45.  * so that M is a power of 2 (see idict.h for details); this allows us to
  46.  * use masking rather than division for computing the initial hash probe.
  47.  * However, C is always the maxlength specified by the client, so clients
  48.  * get a consistent story.
  49.  *
  50.  * As noted above, the keys may be either in packed or unpacked form.
  51.  * The markers for unused and deleted entries are different in the two forms.
  52.  * In the packed form:
  53.  *      unused entries contain packed_key_empty;
  54.  *      deleted entries contain packed_key_deleted.
  55.  * In the unpacked form:
  56.  *      unused entries contain a literal null;
  57.  *      deleted entries contain an executable null.
  58.  *
  59.  * The first entry is always marked deleted, to reduce the cost of the
  60.  * wrap-around check.
  61.  *
  62.  * Note that if the keys slot in the dictionary is new,
  63.  * all the key slots are new (more recent than the last save).
  64.  * We use this fact to avoid saving stores into packed keys
  65.  * for newly created dictionaries.
  66.  *
  67.  * Note that name keys with indices above packed_name_max_index require using
  68.  * the unpacked form.  */
  69. #define dict_is_packed(dct) r_has_type(&(dct)->keys, t_shortarray)
  70. #define packed_key_empty (pt_tag(pt_integer) + 0)
  71. #define packed_key_deleted (pt_tag(pt_integer) + 1)
  72. #define packed_key_impossible pt_tag(pt_full_ref)    /* never matches */
  73. #define packed_name_key(nidx)\
  74.   ((nidx) <= packed_name_max_index ? pt_tag(pt_literal_name) + (nidx) :\
  75.    packed_key_impossible)
  76. /*
  77.  * Using a special mark for deleted entries causes lookup time to degrade
  78.  * as entries are inserted and deleted.  This is not a problem, because
  79.  * entries are almost never deleted.
  80.  */
  81. #define d_maxlength(dct) ((uint)((dct)->maxlength.value.intval))
  82. #define d_set_maxlength(dct,siz) ((dct)->maxlength.value.intval = (siz))
  83. #define nslots(dct) r_size(&(dct)->values)
  84. #define npairs(dct) (nslots(dct) - 1)
  85. #define d_length(dct) ((uint)((dct)->count.value.intval))
  86.  
  87. /*
  88.  * Define macros for searching a packed dictionary.  Free variables:
  89.  *      ref_packed kpack - holds the packed key.
  90.  *      uint hash - holds the hash of the name.
  91.  *      dict *pdict - points to the dictionary.
  92.  *      uint size - holds npairs(pdict).
  93.  * Note that the macro is *not* enclosed in {}, so that we can access
  94.  * the values of kbot and kp after leaving the loop.
  95.  *
  96.  * We break the macro into two to avoid overflowing some preprocessors.
  97.  */
  98. /* packed_search_body also uses kp and kbot as free variables. */
  99. #define packed_search_value_pointer (pdict->values.value.refs + (kp - kbot))
  100. #define packed_search_body(found1,found2,del,miss)\
  101.     { if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);\
  102.       if ( *kp == kpack )\
  103.        { found1;\
  104.      found2;\
  105.        }\
  106.       else if ( !r_packed_is_name(kp) )\
  107.        { /* Empty, deleted, or wraparound. Figure out which. */\
  108.      if ( *kp == packed_key_empty ) miss;\
  109.      if ( kp == kbot ) break;    /* wrap */\
  110.      else { del; }\
  111.        }\
  112.     }
  113. #define packed_search_1(found1,found2,del,miss)\
  114.    const ref_packed *kbot = pdict->keys.value.packed;\
  115.    register const ref_packed *kp;\
  116.    for ( kp = kbot + dict_hash_mod(hash, size) + 1; ; kp-- )\
  117.      packed_search_body(found1,found2,del,miss)
  118. #define packed_search_2(found1,found2,del,miss)\
  119.    for ( kp += size; ; kp-- )\
  120.      packed_search_body(found1,found2,del,miss)
  121.  
  122. #endif /* idictdef_INCLUDED */
  123.